class Solution {
public:
    vector<string> permutation(string s) {
        int sizeOfS = s.size();
        if(sizeOfS < 1 || sizeOfS > 8)  return vector<string>(1, "");

        /*
        在不存在重复字符的情况下，求不同排列总数实质是排列问题；具体操作上，可考虑用递归实现；
        大问题分解成小问题:每个字符串都可分割成1和n-1两个部分，这两部分每次总共有n种排列方法；
        在这两部分交换的过程中若遇到相同字符，则跳过
        */
        vector<string> result;
        string temp = "";
        arrange(result, s, temp, 0, sizeOfS - 1);
        return result;
    }

    /*
    回溯算法：交换法
    [a,[b,c]],[b,[a,c]],[c,[b,a]]
    将首字符与剩余字符依次交换，之后将剩余交换后的字符串递归
    */
    void arrange(vector<string>& result, string& s, string& temp, int first, int last){
        //递归结束条件
        if(first == last){
            temp.push_back(s[last]);
            result.push_back(temp);
            temp.pop_back();
            return;
        }
        for(int i = first; i <= last; ++i){
            //排除重复排列,若要交换的元素是以前已经交换过的，则跳过这一步
            if( i > first){
                int iTemp = first;
                while(iTemp < i){
                    if(s[iTemp] == s[i])  break;
                    ++iTemp;
                }
                if(iTemp < i)  continue;
            }

            swap(s[i], s[first]);
            temp.push_back(s[first]);
            arrange(result, s, temp, first + 1, last);
            swap(s[i], s[first]);  //撤销交换
            temp.pop_back(); 
        }
        return;
    }
};